#include "minHeap.h"

void createMinHeap(minHeap& H, HElemType arr[], int n)
{
	for (int i = 0; i < n; i++)
	{
		H.elem[i] = arr[i];
	}
	H.curSize = n;
	for (int i = (H.curSize - 2) / 2; i >= 0; i--)
	{
		siftDown(H, i, H.curSize - 1);
	}
}

void siftDown(minHeap& H, int i, int m)
{
	HElemType temp = H.elem[i];
	for (int j = 2 * i + 1; j <= m; j = 2 * j + 1)
	{
		if (j<m && H.elem[j]>H.elem[j + 1])
		{
			j++;
		}
		if (temp <= H.elem[j])
		{
			break;
		}
		else
		{
			H.elem[i] = H.elem[j];
			i = j;
		}
	}
	H.elem[i] = temp;
}

bool Insert(minHeap& H, HElemType x)
{
	if (H.curSize == heapSize)
	{
		return false;
	}
	H.elem[H.curSize] = x;
	siftUp(H, H.curSize);
	H.curSize++;
	return true;
}

void siftUp(minHeap& H, int start)
{
	HElemType temp = H.elem[start];
	int j = start;
	int i = (j - 1) / 2;
	while (j > 0)
	{
		if (H.elem[i] <= temp)
		{
			break;
		}
		else
		{
			H.elem[j] = H.elem[i];
			j = i;
			i = (i - 1) / 2;
		}
	}
	H.elem[j] = temp;
}

bool Remove(minHeap& H, HElemType& x)
{
	if (H.curSize == 0)
	{
		return false;
	}
	x = H.elem[0];
	H.elem[0] = H.elem[H.curSize - 1];
	H.curSize--;
	siftDown(H, 0, H.curSize - 1);
	return true;
}